package com.programmercarl.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
 *
 * @author yulongtian
 * @create 2024-12-29 16:03
 */
public class Test03 {
    public static void main(String[] args) {
        Test03 test03 = new Test03();
        System.out.println(test03.letterCombinations("23"));
    }


    private final String[] letterMap = {
            "", // 0
            "", // 1
            "abc", // 2
            "def", // 3
            "ghi", // 4
            "jkl", // 5
            "mno", // 6
            "pqrs", // 7
            "tuv", // 8
            "wxyz", // 9
    };

    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits.isEmpty()) {
            return res;
        }
        StringBuilder sb = new StringBuilder();
        backTracking(digits, 0, res, sb);
        return res;
    }

    public void backTracking(String digits, int index, List<String> res, StringBuilder sb) {
        if (index == digits.length()) {
            res.add(sb.toString());
            return;
        }

        char c = digits.charAt(index);
        String s = letterMap[c - '0'];
        for (int j = 0; j < s.length(); j++) {
            sb.append(s.charAt(j));
            int len = sb.length();
            backTracking(digits, index + 1, res, sb);
            sb.deleteCharAt(len - 1);
        }

    }


}
